1. Field of the Invention
The present invention is directed to a system for pathfinding.
2. Description of the Related Art
Computers have revolutionized the idea of modeling systems for enhanced study and use of the systems. One example is the modeling of a system as a network. A network is defined in its most general sense as something that includes a number of paths that interconnect or branch out. Many systems that involve decisions can be modeled as a network. For example, a manufacturing process or a system for providing medical treatment can be modeled as a network of decision points and actions between decision points. This network can be represented in electronic form and stored on a processor readable storage medium so that software can be created for using the network model to study or use the system.
Another example of a useful network that can be stored in electronic form is the electronic map, which includes geographically referenced electronic data quantifying a physical, social or economic system. The range of information included in electronic maps is unlimited. For example, an electronic map of roads could include distances between elements, travel time, lot numbers, tax information, tourist information, processing time, waiting time, etc. Additionally, storing a map as a file on a computer allows for unlimited software applications to manipulate that data.
One advantage of the electronic map is that it can store and determine costs associated with various portions of a map. A cost is a variable that can be minimized or maximized. Note that the costs are not necessarily monetary costs. Typically costs are represented as integers. Sometimes costs can be represented as real numbers or non-standard numbers. Additional information about costs and non-standard numbers can be found in U.S. patent application Ser. No. 08/756,263, "Using Multiple Levels Of Costs For A Pathfinding Computation," filed Nov. 25, 1996, now issued as U.S. Pat. No. 5,890,081 incorporated herein by reference. Examples of costs include time, distance, tolls paid, ease of turning, quality of scenery, etc.
Electronic maps, as well as other networks, can also be used for pathfinding, which is a method for computing a route between an origin and a destination. Some systems compute recommended routes and guide the driver by highlighting the recommended route on a map display, or by giving turn-by-turn directions (via paper or display), or both.
When a pathfinding system is computing a recommended route to a destination, it does so by finding the most desirable route according to certain specified criteria. These criteria may be specified by the driver, or may be set as defaults at the time of manufacture. Often, a system will be used to find a path that minimizes (or maximizes) some cost, for example, driving time.
An electronic map that is used for pathfinding must carry information about the connectivity of a road network, that is, information about the ways in which pieces of road do or do not connect to each other, for example, where there are ordinary intersections, where there are overpasses, where turns are restricted, and so on. For an area of any significant extent, this is a very large amount of information. An electronic map can include tens or hundreds of megabytes of data. In order to hold such vast quantities of data economically and allow a user to replace maps with updated copies easily, many current pathfinding apparatus (which includes general purpose computers with pathfinding software, automotive navigation systems or other map application equipment) use CD-ROMs to store the electronic map data.
Although CD-ROMs hold a great deal of data, accessing that data can be relatively slow. If a pathfinding system has to wait for a CD-ROM to be accessed every time it needs data, the time needed to compute a path becomes unacceptable to a user. A user of a navigational pathfinding system stored in a car typically would demand very fast response times when requesting a path because a user currently driving needs to know which way to turn. For these reasons, it is very important to minimize the number of disk accesses required to compute a path. It is noted that some systems may use peripheral devices other than CD-ROMs, for example, hard disks, floppy disks, solid state memory, DVD, mini disks, etc. These other storage devices suffer similar access time limitations.
One attempt to minimize the number of disk accesses required to compute a path includes grouping map data into clusters, that is, grouping together on a CD-ROM (or other storage device) information about sets of road segments often used in the same path computation. For example, a number of consecutive segments of the same street, road segments that cross each other or road segments that lead to a highway may be stored in a single cluster. Note that these clusters need not be geographically based. Information about roads on two sides of a river in an area that is not close to a bridge would probably not be stored in the same cluster, since the roads would not be used in relation to each other during path calculation even though they may be quite close to each other geographically. Information about highways over a wide area are good candidates to be stored together in one cluster because a path computation typically explores the connections of highways with other highways. There are many ways to cluster data to increase performance. When clustering is used with a suitable cache methodology, the time for pathfinding is saved because information needed by the pathfinding computation is often already in the cache having been read as part of a cluster which includes data already used. More information about using a cache strategy can be found in U.S. patent application Ser. No. 08/802,733, "Caching For Pathfinding Computation," filed Feb. 20, 1997, incorporated herein by reference.
Pathfinding remains a lengthy process even when using a cache. Every cluster used in the computation still needs to be read at least once. Since the pathfinding computation may need to read a large number of clusters at the beginning of and during the pathfinding computation, the user of the pathfinding apparatus still spends a significant amount of time waiting for the pathfinding apparatus to read all the data prior to a path being calculated.
Another attempt to speed up the pathfinding process is to pre-compute certain paths in a network or map. To find a path from an origin to a destination, a system would pick an appropriate pre-computed path, find a path from the origin to the pre-computed path, and find a path from the pre-computed path to the destination. More discussion about using pre-computed paths can be found in U.S. patent application Ser. No. 08/756,258, "Method For Determining Exits and Entrances For A Region In A Network," filed Nov. 25, 1996, now issued as U.S. Pat. No. 5,916,299, incorporated herein by reference. Although using a pre-computed path will speed up a pathfinding process, a lot of processing time is still used to find a path from an origin to the pre-computed path and from the pre-computed path to a destination.
Therefore, a system is needed that reduces the amount of time needed to perform a pathfinding process.